package org.example.struct.array2;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author liyishan
 * @date 2023/10/17 10:00
 * @apiNote
 */

public class Test00792NumMatchingSubseq {

    public static void main(String[] args) {
        String s = "dsahjpjauf";
        String[] words = new String[]{"ahjpjau","ja","ahbwzgqnuk","tnmlanowax"};
        int res = test(s, words);
        System.out.println(res);
    }

    public static int test(String s, String[] words) {
        int n = words.length;
        int count = 0;
        for(int i=0;i<n;i++){
            char[] chars = words[i].toCharArray();
            int size = 0;
            boolean flag = true;
            for(int j = 0;j<chars.length;j++){
                while(size <s.length() && chars[j] != s.charAt(size)){
                    size++;
                }
                if(size == s.length() ){
                    flag = false;
                    break;
                }else{
                    size++;
                }
            }
            if(flag){
                count++;
            }
        }
        return count;
    }


    public static int numMatchingSubseq(String s, String[] words) {
        Queue<int[]>[] p = new Queue[26];
        for (int i = 0; i < 26; ++i) {
            p[i] = new ArrayDeque<int[]>();
        }
        for (int i = 0; i < words.length; ++i) {
            p[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});
        }
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            int len = p[c - 'a'].size();
            while (len > 0) {
                int[] t = p[c - 'a'].poll();
                if (t[1] == words[t[0]].length() - 1) {
                    ++res;
                } else {
                    ++t[1];
                    p[words[t[0]].charAt(t[1]) - 'a'].offer(t);
                }
                --len;
            }
        }
        return res;
    }
}
